package leetcode;

import javax.print.attribute.standard.NumberUp;
import java.util.*;

class ListNode2{
    String  val;
    ListNode2 next;
    public ListNode2(String  val){
        this.val=val;
    }
}
public class LeetCodeMain70 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            int num=in.nextInt();
            System.out.printf("%d =",num);
            for (int i = 2; i <= Math.sqrt(num); i++) {
                while(num!=i)
                {
                    if(num%i==0)
                    {
                        System.out.printf("%d * ",i);
                        num/=i;
                    }
                    else
                        break;
                }
            }
            System.out.printf("%d\n",num);

        }
    }
    public static List<Integer> list1=new ArrayList<>();
    public static List<Integer> list=new ArrayList<>();
    public static int count=0;
    public static void main8(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            int num=in.nextInt();
            int[] arr=isNum(num);
//            for (int num2:arr) {
//                System.out.println(num2);
//            }
            back(arr,1,0,num);
//            Collections.sort(list);
            System.out.printf("%d =",num);
            for (int i = 0; i < list.size()-1; i++) {
                System.out.printf(" %d *",list.get(i));
            }
            System.out.printf(" %d\n",list.get(list.size()-1));
            while (!list.isEmpty()){
                list.remove(0);
            }
            count=0;
        }
    }
    public static void back(int[] arr,int mul,int startIndex,int num){
        if (mul==num){
            for (int n:list1) {
                list.add(n);
            }
            count=1;
            return;
        }
        if (mul>num){
            return;
        }
        for (int i = startIndex; i < arr.length&&count!=1; i++) {
            list1.add(arr[i]);
            mul*=arr[i];
            back(arr, mul, i, num);
            mul/=arr[i];
            list1.remove(list1.size()-1);
        }

    }
    public static int[] isNum(int num){
        List<Integer> list=new ArrayList<>();
        for (int i =num ; i >= 2; i--) {
            int count=0;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i%j==0){
                    count=1;
                    break;
                }
            }
            if (count==0){
                list.add(i);
            }
        }
        int[] arr=new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i]=list.get(i);
        }
        return arr;
    }
    public static void main7(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] arr=new int[n];
        for (int i = 0; i < n; i++) {
            arr[i]=in.nextInt();
        }
        int first=arr[0];
        boolean flag=false;
        int second=Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            if (arr[i]<first){
                first=arr[i];
                second=Integer.MAX_VALUE;
            }else if (arr[i]>first&&arr[i]<second){
                second=arr[i];
            }else if (arr[i]>first&&arr[i]>second){
                flag=true;
                break;
            }
        }
        System.out.println(flag);
    }
    public static void main6(String[] args) {
        Scanner in=new Scanner(System.in);
        ListNode2 node=new ListNode2("-1");
        ListNode2 node2=node;
        String string=in.nextLine();
        int k=in.nextInt();
        String[] s1=string.split(" ");
        for (int i = 0; i < s1.length-1; i++) {
            ListNode2 node21=new ListNode2(s1[i]);
            node2.next=node21;
            node2=node2.next;
        }
        node2.next=null;

        Stack<ListNode2> stack=new Stack<>();
        node=node.next;
        ListNode2 node3=new ListNode2("-1");
        ListNode2 node4=node3;
        while (node!= null){
            stack.push(node);
            node=node.next;
            if (stack.size()==k){
                while (!stack.isEmpty()){
                    node4.next=stack.pop();
                    node4=node4.next;
                }
            }
        }
        if (!stack.isEmpty()){
            for (ListNode2 n1:stack) {
                node4.next=n1;
                node4=node4.next;
            }
        }
        node4.next=null;
        node3=node3.next;
        StringBuilder builder=new StringBuilder();
        while (node3.next!=null){
            builder.append(node3.val);
            builder.append("->");
            node3=node3.next;
        }
        builder.append(node3.val);
        System.out.println(builder.toString());
    }
    public static void main5(String[] args) {
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        String[] arr=str.split("-");
        int count=0;
        int year=Integer.parseInt(arr[0]);
        int month=Integer.parseInt(arr[1]);
        int day=Integer.parseInt(arr[2]);
        if (year%400==0||year%4==0&&year%100!=0){
            count++;
        }
        int sum=0;
        int[] arr1={0,31,28,31,30,31,30,31,31,30,31,30,31};
        if (count==1){
            arr1[2]=29;
        }
        for (int i = 1; i < month; i++) {
            sum+=arr1[i];
        }
        sum+=day;
        System.out.println(sum);
    }
    public static void main4(String[] args) {
        Scanner in=new Scanner(System.in);
        String word1=in.nextLine();
        String word2=in.nextLine();
        String s1=word1.substring(0,word1.indexOf("+"));
        String s2=word2.substring(0,word2.indexOf("+"));
        int sum1=Integer.parseInt(s1)*Integer.parseInt(s2);
        String s3=word1.substring(word1.indexOf("+")+1,word1.length()-1);
        String s4=word2.substring(word2.indexOf("+")+1,word2.length()-1);
        if (s3.length()==0){
            s3="1";
        }if (s4.length()==0){
            s4="1";
        }if (s3.equals("-")){
            s3="-1";
        }if (s4.equals("-")){
            s4="-1";
        }
        int sum2=Integer.parseInt(s3)*Integer.parseInt(s4)*-1;
        int num1=sum1+sum2;
        int sum3=Integer.parseInt(s1)*Integer.parseInt(s4);
        int sum4=Integer.parseInt(s2)*Integer.parseInt(s3);
        int num2=sum3+sum4;
        StringBuilder builder=new StringBuilder();
        builder.append(num1);
        builder.append("+");
        builder.append(num2);
        builder.append("i");
        System.out.println(builder.toString());
    }
    public static void main3(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            int num=in.nextInt();
            int count=0;
            for (int i = 2; i <= Math.sqrt(num); i++) {
                if (num%i==0){
                    while (num%i==0){
                        num/=i;
                    }
                    count++;
                }
            }
            if (num!=1){
                count++;
            }
            System.out.println(count);
        }
    }
    public static void main2(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            String str=in.nextLine();
            StringBuilder builder=new StringBuilder();
            for (int i = 0; i < str.length(); i++) {
                char ch=str.charAt(i);
                if (ch>='A'&&ch<='Z'){
                    switch (ch){
                        case 'A':
                            builder.append('V');
                            break;
                        case 'B':
                            builder.append('W');
                            break;
                        case 'C':
                            builder.append('X');
                            break;
                        case 'D':
                            builder.append('Y');
                            break;
                        case 'E':
                            builder.append('Z');
                            break;
                        default:
                            char ch1= (char) (ch-5);
                            builder.append(ch1);
                            break;
                    }
                }else {
                    builder.append(ch);
                }
            }
            System.out.println(builder.toString());
        }
    }
    public static void main1(String[] args) {
        Integer i01=59;
        int i02=59;
        Integer i03=Integer.valueOf(59);
        Integer i04=new Integer(59);
        System.out.println(i03==i04);
    }
    public static int getFirstUnFormedNum(int[] arr) {
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max += arr[i];
            if (min > arr[i]) {
                min = arr[i];
            }
        }
        int[][] dp = new int[arr.length+1][max+1];
        dp[1][1] = 1;
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 1; j <= max; j++) {

                if (j < arr[i-1]) {
                    dp[i][j] = dp[i-1][j];
                }
                else if (j == arr[i-1]) {
                    dp[i][j] = 1;
                }
                else {
                    if (dp[i-1][j-arr[i-1]] == 1) {
                        dp[i][j] = 1;
                    }else if (dp[i-1][j] == 1) {
                        dp[i][j] = 1;
                    }
                    else {
                        dp[i][j] = 0;
                    }
                }
            }
        }
        int index = arr.length;
        for (int i = min; i <= max; i++) {
            if (dp[index][i] != 1) {
                return i;
            }
        }
        return max+1;
    }

}
